public class Test2 {
    //leetcode 岛屿数量
    //https://leetcode.cn/problems/number-of-islands/description/?envType=problem-list-v2&envId=depth-first-search
    boolean[][] vis;
    int[] x = {0,0,-1,1};
    int[] y = {-1,1,0,0};
    public int numIslands(char[][] grid) {
        int row = grid.length, col = grid[0].length;
        vis = new boolean[row][col];
        int ret = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (!vis[i][j] && grid[i][j] == '1') {
                    dfs(grid,i,j);
                    ret++;
                }
            }
        }
        return ret;
    }

    private void dfs(char[][] grid, int row, int col) {
        vis[row][col] = true;
        for (int i = 0; i < 4; i++) {
            int x1 = row + x[i], y1 = col + y[i];
            if (x1 >= 0 && x1 < grid.length && y1 >= 0 && y1 < grid[0].length
                    && !vis[x1][y1] && grid[x1][y1] == '1') {
                dfs(grid,x1,y1);
            }
        }
    }

    public static void main(String[] args) {
        char[][] grid = new char[4][5];
        grid[0][0] = '1';
        grid[0][1] = '1';
        grid[0][2] = '1';
        grid[0][3] = '1';
        grid[0][4] = '0';
        grid[1][0] = '1';
        grid[1][1] = '1';
        grid[1][2] = '0';
        grid[1][3] = '1';
        grid[1][4] = '0';
        grid[2][0] = '1';
        grid[2][1] = '1';
        grid[2][2] = '0';
        grid[2][3] = '0';
        grid[2][4] = '0';
        grid[3][0] = '0';
        grid[3][1] = '0';
        grid[3][2] = '0';
        grid[3][3] = '0';
        grid[3][4] = '0';
        Test2 test2 = new Test2();
        test2.numIslands(grid);
    }
}
